| 翻訳と辞書 |
| Bin (computational geometry) ： ウィキペディア英語版 |
Bin (computational geometry)
In computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis-aligned rectangles on a 2D plane, answers the question: ''"Given a query rectangle, what are the rectangles intersecting it?"''. ''k''-d tree is another data structure that can answer this question efficiently. In the example in the figure, ''A, B, C, D, E'' and ''F'' are existing rectangles, the query with the rectangle ''Q'' should return ''C, D, E'' and ''F'', if we define all rectangles as closed intervals.
The data structure partitions a region of the 2D plane into uniform-sized ''bins''. The bounding box of the bins encloses all ''candidate'' rectangles to be queried. All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects. For example, in the figure, candidate ''B'' has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a singly linked list. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list.
== Operations ==
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Bin (computational geometry)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|